package competition;

import java.util.HashMap;
import java.util.Map;

public class compe_250 {
    public static void main(String[] args) {
        Solution_com250 p=new Solution_com250();
        int[][] nums = new int[3][2];
        nums[0][0] = 1;
        nums[0][1] = 5;
        nums[1][0] = 3;
        nums[1][1] = 2;
        nums[2][0] = 4;
        nums[2][1] = 2;

        long result = p.maxPoints(nums);
        System.out.println(result);
    }
}

class Solution_com250 {

    // 键盘问题
    public int canBeTypedWords(String text, String brokenLetters) {
        Map<String, Integer> stringMap = new HashMap<>();
        // 拿到错误的记录
        for(int i=0; i<brokenLetters.length(); i++){
            String tmp = String.valueOf(brokenLetters.charAt(i));
            if(!stringMap.containsKey(tmp)){
                stringMap.put(tmp, 1);
            }
        }

        // 循环Text文本
        String[] stringList = text.split(" ");
        int count = 0;
        for(int i=0; i<stringList.length; i++){
            String textValue = stringList[i];
            // 这个是否可以输出
            boolean isValue = true;
            for(int j=0; j<textValue.length(); j++){
                // 拿出每一个字符
                String tmp = String.valueOf(textValue.charAt(j));
                if(stringMap.containsKey(tmp)){
                    isValue = false;
                    // 如果被包含在错误键位中就无法按键
                    break;
                }
            }
            if(isValue){
                // 输出一个
                count = count+1;
            }
        }
        return count;
    }

    // 新增台阶问题
    public int addRungs(int[] rungs, int dist) {
        // 本身就是在顶自然直接过
        if(rungs.length==0){return 0;}
        // 台阶数
        int levelNum = 0;
        // 特殊考虑首个台阶
        for(int i=-1; i<rungs.length-1; i++){
            if(i!=-1) {
                // 下一层台阶 与 本身的台阶的差距
                int distance = rungs[i + 1] - rungs[i];
                // 代表你这里需要加几个
                // 只有差距大于dist时才开始
                while(distance > dist){
                    distance = distance - dist;
                    levelNum = levelNum + 1;
                }
            }else{
                // 考虑0的情况
                int distance = rungs[i+1] - 0;
                while(distance > dist){
                    distance = distance - dist;
                    levelNum = levelNum + 1;
                }
            }
        }
        return levelNum;
    }

    // 扣分后的最大得分
    public long maxPoints(int[][] points) {
        if(points.length==0){return 0;}
        // 使用动态规划
        // 构建dp数组  每个位置代表这个位置的最高分是多少 最后选取最高分即完成

        long maxScore = 0; // 最高分
        int maxNumJ = 0; // 上层最高的分的 第二个数组索引下标 J

        long[][] dp = new long[points.length][points[0].length];
        for(int j=0; j<points[0].length; j++){
            // 首行不考虑减分问题
            dp[0][j] = points[0][j];
            if(maxScore < dp[0][j]){
                maxScore = dp[0][j];
                maxNumJ = j;
            }
        }
        // 计算方式 本格子最高分 = 上层每一个格子最高分 + 我的分 - 我的距离
        for(int i=1; i<points.length; i++){
            // 找到这一层最高分
            long maxJScore = 0;
            // 循环遍历每一个格子
            for(int j=0; j<points[i].length; j++){
                long tmpScore = 0;
                // 上层格子  只计算  maxNumJ~j~maxNumJ
                for(int k=0; k<points[i-1].length; k++){
                    if(Math.abs(j-k) > Math.abs(j-maxNumJ)){
                        continue;
                    }
                    // 格子之间的距离
                    int distance = Math.abs(j-k);
                    // 分数 = 本格子的分数(point) + 上层的分数(dp) - 距离
                    long score =  points[i][j] + dp[i-1][k] - distance;
                    if(tmpScore < score){
                        tmpScore = score;
                    }
                }
                // 这个为最大的加入数组中
                dp[i][j] = tmpScore;

                if(maxJScore < tmpScore){
                    maxJScore = tmpScore;
                    maxNumJ = j;
                }

                if(maxScore < tmpScore){
                    maxScore = tmpScore;
                }
            }
        }
        return maxScore;
    }
}